<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>Longest Substring with At Least K Repeating Characters</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-body vscode-light">
        <h1 id="longest-substring-with-at-least-k-repeating-characters">Longest Substring with At Least K Repeating Characters</h1>
<h1 id="1-lc-395-longest-substring-with-at-least-k-repeating-characters">1. LC 395. Longest Substring with At Least K Repeating Characters</h1>
<ul>
<li><a href="https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/">https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/</a></li>
</ul>
<p>Given a string s and an integer k, return the length of the longest substring of s such that the frequency of each character in this substring is greater than or equal to k.</p>
<pre><code><code><div>Example 1:

Input: s = &quot;aaabb&quot;, k = 3
Output: 3
Explanation: The longest substring is &quot;aaa&quot;, as 'a' is repeated 3 times.
Example 2:

Input: s = &quot;ababbc&quot;, k = 2
Output: 5
Explanation: The longest substring is &quot;ababb&quot;, as 'a' is repeated 2 times and 'b' is repeated 3 times.
 

Constraints:

1 &lt;= s.length &lt;= 104
s consists of only lowercase English letters.
1 &lt;= k &lt;= 105
</div></code></code></pre>
<p>本地暴力解法 O(n^2 * 26)</p>
<h2 id="滑动窗口法">滑动窗口法</h2>
<p>最好的解法还是用滑动窗口解法。 关键是这个滑动窗口如何移动的问题。 所以本地需要分解为子问题。</p>
<ol>
<li>查找最长的子字符串， 里面只包含1种字符，而且每种字符的数量不少于k</li>
<li>查找最长的子字符串， 里面只包含2种字符，而且每种字符的数量不少于k</li>
<li>查找最长的子字符串， 里面只包含3种字符，而且每种字符的数量不少于k</li>
<li>...</li>
</ol>
<p>如果原始字符串s里面包含d种字符，我们就要用滑动窗口法遍历d次， 最后的时间复杂度就是d * n, 其中n是s的长度</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">longestSubstring</span>(<span class="hljs-params">self, s: str, k: int</span>) -&gt; int:</span>
        d = len(collections.Counter(s))
        
        n = len(s)
        ans = <span class="hljs-number">0</span>
        <span class="hljs-keyword">for</span> unique_limit <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, d+<span class="hljs-number">1</span>):
            m = collections.defaultdict(int)
            start = <span class="hljs-number">0</span>
            end = <span class="hljs-number">0</span>
            unique = <span class="hljs-number">0</span>
            unique_k = <span class="hljs-number">0</span>
            <span class="hljs-keyword">while</span> end &lt; n:
                <span class="hljs-keyword">if</span> unique &lt;= unique_limit:
                    m[s[end]] += <span class="hljs-number">1</span>
                    <span class="hljs-keyword">if</span> m[s[end]] == <span class="hljs-number">1</span>:
                        unique += <span class="hljs-number">1</span>
                    <span class="hljs-keyword">if</span> m[s[end]] == k:
                        unique_k += <span class="hljs-number">1</span>
                    end += <span class="hljs-number">1</span>
                <span class="hljs-keyword">else</span>:
                    m[s[start]] -= <span class="hljs-number">1</span>
                    <span class="hljs-keyword">if</span> m[s[start]] == <span class="hljs-number">0</span>:
                        unique -= <span class="hljs-number">1</span>
                    <span class="hljs-keyword">if</span> m[s[start]] == k - <span class="hljs-number">1</span>:
                        unique_k -= <span class="hljs-number">1</span>
                    start += <span class="hljs-number">1</span>
                
                <span class="hljs-keyword">if</span> unique == unique_k:
                    ans = max(ans, end - start)
        <span class="hljs-keyword">return</span> ans
    
</div></code></pre>
<h2 id="分治方法">分治方法</h2>
<p>时间复杂度还是 O(n^2)</p>
<pre><code class="language-python"><div><span class="hljs-keyword">from</span> collections <span class="hljs-keyword">import</span> Counter
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">longestSubstring</span>(<span class="hljs-params">self, s: str, k: int</span>) -&gt; int:</span>
        c = Counter(list(s))
        <span class="hljs-keyword">for</span> key <span class="hljs-keyword">in</span> c.keys():
            <span class="hljs-keyword">if</span> c[key] &lt; k:
                <span class="hljs-keyword">return</span> max([self.longestSubstring(s2,k) <span class="hljs-keyword">for</span> s2 <span class="hljs-keyword">in</span> s.split(key)])
        <span class="hljs-keyword">return</span> len(s)
    
</div></code></pre>

    </body>
    </html>